/**
 * Copyright (C) 2016, Daniel Thuerck
 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
 * All rights reserved.
 *
 * This software may be modified and distributed under the terms
 * of the BSD license. See the LICENSE file for details.
 */

#ifndef __MAPMAP_TREE_H_
#define __MAPMAP_TREE_H_

#include <memory>
#include <vector>
#include <iterator>

#include "header/defines.h"
#include "header/vector_types.h"
#include "header/graph.h"

NS_MAPMAP_BEGIN

template<typename COSTTYPE>
struct TreeNode
{
    bool is_in_tree;

    luint_t parent_id;
    luint_t to_parent_edge_id;
    scalar_t<COSTTYPE> to_parent_weight;

    luint_t node_id;
    luint_t degree;
    luint_t dependency_degree;

    const luint_t * children_ids;
    const luint_t * dependency_ids;
    const luint_t * dependency_edge_ids;
    const COSTTYPE * dependency_weights;
};

/**
 * Represents a directed tree. All data is saved in SoA format, but returned
 * to the reader as AoS.
 * While building, access to the raw members is allowed (until finalize())
 * called, which gathers children per node and disables modification.
 *
 * This tree is supposed to be a layer above an undirected graph, thus
 * it allocates space for one tree node per graph node.
 *
 * Assumes that number of nodes < INVALID.
 */
template<typename COSTTYPE>
class Tree
{
public:
    Tree(const luint_t graph_num_nodes,
        const luint_t graph_num_edges);
    ~Tree();

    /**
     * Get a struct representation of a node (not necessarily in the tree!).
     */
    const TreeNode<COSTTYPE> node(const luint_t& node_id) const;

    /* Determine number of nodes in the tree */
    const luint_t num_nodes() const;

    /* Determine number of nodes in the underlying graph */
    const luint_t num_graph_nodes() const;

    /**
     * Deactivates access to the internal structures and assembles a
     * list of children for each node.
     */
    void finalize(const bool compute_dependencies,
        const Graph<COSTTYPE> * graph);

    /**
     * Accessors to raw data structures.
     */
    std::vector<luint_t>& raw_parent_ids();
    std::vector<luint_t>& raw_to_parent_edge_ids();
    std::vector<COSTTYPE>& raw_weights();

    /* these will be generated by finalize() */
    std::vector<luint_t>& raw_degrees();
    std::vector<luint_t>& raw_children_offsets();
    std::vector<luint_t>& raw_children_list();
    std::vector<luint_t>& raw_dependency_offsets();
    std::vector<luint_t>& raw_dependency_list();
    std::vector<luint_t>& raw_dependency_edge_id_list();
    std::vector<luint_t>& raw_dependency_degrees();

protected:
    luint_t m_num_nodes;
    luint_t m_graph_nodes;
    bool m_enable_modify;

    /**
     * Convention:
     * - parent_id == node_id <=> node is root
     * - parent_id == INVALID <=> node is not in tree
     */
    std::vector<luint_t> m_parent_id;
    std::vector<luint_t> m_parent_edge_id;
    std::vector<luint_t> m_degree;
    std::vector<luint_t> m_children_offset;
    std::vector<luint_t> m_children_list;
    std::vector<COSTTYPE> m_weight;

    std::vector<luint_t> m_dependency_degree;
    std::vector<luint_t> m_dependency_offset;
    std::vector<luint_t> m_dependency_list;
    std::vector<luint_t> m_dependency_edge_id_list;
    std::vector<COSTTYPE> m_dependency_weight;
};

NS_MAPMAP_END

#include "source/tree.impl.h"

#endif /* __MAPMAP_TREE_H_ */